﻿#include<iostream>
#include<stdexcept>
#include "Person.h"

struct LinkedList {
	LinkedList* next;
	int val;

	LinkedList(int x) :val(x), next(nullptr) {
	}
	//插入节点，在node节点后插入新节点
	void Insert(LinkedList* node, LinkedList* p) {
		//获得当前节点的next节点
		LinkedList* next = node->next;
		//将当前节点的next节点指向新节点
		node->next = p;
		//将新节点的next节点指向原来的next节点
		p->next = next;
	}
	//删除节点，在node节点后删除节点
	void Delete(LinkedList* node) {
		if (node->next == nullptr)
			return;
		LinkedList* delNode = node->next;
		LinkedList* nextNode = delNode->next;
		node->next = nextNode;
		//释放内存
		delete delNode;
	}
	//访问节点，访问第n个节点，时间复杂度O(n)
	LinkedList* Get(LinkedList* head, int index) {
		if (head == nullptr)
			throw std::out_of_range("linkedlist is empty");
		for (int i = 0; i < index; i++) {
			head = head->next;
		}
		return head;
	}
	//查找节点，也是访问节点的一种
	int find(LinkedList* head, int findValue) {
		int index = 0;
		while (head!=nullptr) {
			if (head->val == findValue)
				return index;
			head = head->next;
			index++;
		};
		return -1;
	}
};

//基于链表实现栈，链表表头进行插入和删除
class LinkedListStack {
private:
	LinkedList* head;
	int stackSize;
public:
	LinkedListStack() {
		head = nullptr;
		stackSize = 0;
	}
	~LinkedListStack() {
		freeMemoryStack(head);
	}
	//删除链表
	void freeMemoryStack(LinkedList* node) {
		if (node == nullptr)
			return;
		while (node->next != nullptr) {
			LinkedList* delNode = node;
			node = node->next;
			delete delNode;
		}
	}
	//获取栈长度
	int getSize() {
		return stackSize;
	}
	//判断栈是否为空
	bool isEmpty() {
		return stackSize == 0 ? true : false;
	}
	//入栈
	void push(int num) {
		LinkedList* newNode = new LinkedList(num);
		newNode->next = head;
		head = newNode;
		stackSize++;
	}
	//出栈
	int pop() {
		int num = getTop();
		LinkedList* popNode = head;
		head = head->next;
		delete popNode;
		stackSize--;
		return num;
	}
	//获取栈顶元素值
	int getTop() {
		if (isEmpty())
			throw std::out_of_range("stack is empty");
		int val = head->val;
		return val;
	}
};


int main() {
	std::cout << "----Cpp Stack----" << std::endl;
	Person* alice = new Person("alice", 18);
	alice->introduce();
	alice->setName("J.Alice");
	alice->celebrateBirthday();

	std::cin.get();
}